package com.leetcode.dp;

public class NumDistinct {
    public static void main(String[] args) {

    }

    public int numDistinct(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        if (sLen < tLen) {
            return 0;
        }
        int[][] dp = new int[sLen + 1][tLen + 1];
        for (int i = 0; i <= sLen; i++) {
            dp[i][tLen] = 1;
        }
        for (int i = sLen - 1; i >= 0; i--) {
            char sCh = s.charAt(i);
            for (int j = tLen - 1; j >= 0; j--) {
                char tCh = t.charAt(j);
                if (sCh == tCh) {
                    dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];
                } else {
                    dp[i][j] = dp[i + 1][j];
                }
            }
        }
        return dp[0][0];
    }
}
